from typing import List


class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        # dp[i][j] 代表 第 i 位 和 第 n - j 位 之间 最大的子序列数
        '''
        
        用dp[i][j] 表示字符串sss的下标范围[i, j]内的最长回文子序列的长度
        '''

        dp = [[0] * (n + 1) for i in range(n + 1)]
        ss = s[::-1]

        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if s[i - 1] == ss[j - 1]:
                    '''
                    
                    对于dp[i][j] 来说，如果当前相等，那么扩大范围也应该是相等的，即 dp[i - 1][j - 1] + 1
                    其中 dp[i][j] 中的 i 代表正序的索引加一的位置，j代表逆序索引加一的位置
                    
                    '''
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    '''
                    如果 s[i - 1] == ss[j - 1] 不相等，即 第 i-1 位 和 n - i -1 位不相等(正数第 x 位和 倒数第 x 位)
                                        
                    '''
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
            #     print_array(dp)
            # print("=================")

        '''
        dp [n][n] 代表了 正序的最后一位，到逆序的最后一位中最大的子序列数 即 第一位到最后一位中 最大子序列数
        '''
        return dp[n][n]


def print_array(array: []):
    for i in array:
        for x in i:
            print(x, end=",")
        print()
    print()


if __name__ == '__main__':
    nums = 'abvcv'
    solution = Solution()
    print(solution.longestPalindromeSubseq(nums))

# 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
#
# 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
#
#
#
# 示例
# 1：
#
# 输入：s = "bbbab"
# 输出：4
# 解释：一个可能的最长回文子序列为
# "bbbb" 。
